import java.util.ArrayList;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Random;


public class Map {
        public ArrayList<MapNode> nodes = new ArrayList<MapNode>();
        public ArrayList<Edge> edges = new ArrayList<Edge>();
        public TerrainType[][] tiles;
        //public ArrayList<Quest> allQuests = new ArrayList<Quest>();
       
        public ArrayList<Pet> allPets = new ArrayList<Pet>();
        
        
        
        public Map(int rows, int cols, Player player) {
        	//generateQuests(player.seed);
            
            getPetList();
        	generateMap(player, rows, cols);
            computePaths();
            computeDistanceToNodes();
            
            /* Tränare måste genereras efter computeDistanceToNodes
             * så deras pets inte beräknas på infinite avstånd */
            for (MapNode n : nodes) {
            	n.generateTrainer(player.seed);
            }
            
            /* distribute quests over nodes wee */
            //distributeTopLevelQuestsOverNodes(player);
            //updateActiveQuests(player);
        }
        
        public MapNode getNode(int index) {
                return nodes.get(index);
        }
        
        public boolean adjacent(MapNode a, MapNode b) {
        	if (a == b) {
        		return true;
        	}
        	for (Edge e : edges) {
        		if (e.spanning(a, b)) {
        			return true;
        		}
        	}
        	
        	return false;
        }
        
        private boolean connected(MapNode a, MapNode b) {
            LinkedList<MapNode> toDoSet = new LinkedList<MapNode>();
            LinkedList<MapNode> doneSet = new LinkedList<MapNode>();
           
            toDoSet.add(a);
           
            while (!toDoSet.isEmpty()) {
                    MapNode t = toDoSet.poll();
                    doneSet.add(t);
                    for (Edge e : edges) {
                            if (e.involves(t)) {
                                    MapNode reachable = e.other(t);
                                    if (reachable == b) {
                                            return true;
                                    }
                                    if (!doneSet.contains(reachable)) {
                                            toDoSet.add(reachable);
                                    }
                            }
                    }
            }
           
            return false;
        }
        
        /* 
         * ----------------------
         * QUEST GENERATION STUFF
         * ----------------------
         
        
        public void generateQuests(Random seed) {        	
        	int i = seed.nextInt(5)+7;

        	for (int j = 0; j < i; j++){
        		new Quest(this, seed);
        	}
        }
        
        public void distributeTopLevelQuestsOverNodes(Player player) {
        	ArrayList<MapNode> remainingNodes = new ArrayList<MapNode>(nodes);
        	ArrayList<Quest> needsToBeDistributed;
            
        	/* Distribute quests as long as there is room 
            for (int i = 0; i < allQuests.size() && !remainingNodes.isEmpty(); i++) {
            	Quest q = allQuests.get(i);
            	
            	/* if a quest is not yet distributed 
            	if (q.nodeIndex == -1) {
            		/* distribute it while checking which of
            		 * its children need to be distributed 
            		needsToBeDistributed = q.setNodeIndex(remainingNodes.get(0).index);
            		
            		/* as it is a "top level quest", set it to be active 
            		remainingNodes.get(0).activeQuestIndex = i;
            		
            		/* Take a backup of the current state of remaining nodes,
            		 * if the distribution fails, restore this backup so further
            		 * quests can be distributed instead of this 
            		ArrayList<MapNode> remainingBackup = new ArrayList<MapNode>(remainingNodes);
            		
            		/* The node is no longer home to further
            		 * active quests. 
            		remainingNodes.remove(0);
            		
            		/* Distribute the children of the quest
            		 * over other nodes 
            		if (!distributeAlternativeQuestsOverNodes(needsToBeDistributed, remainingNodes)) {
            			/* if there is no room for the child quests,
            			 * revert all the changes done by this quest
            			 * and just go on and try to distribute the
            			 * next quest in case there's room 
            			remainingNodes = remainingBackup;
            			remainingNodes.get(0).activeQuestIndex = -1;
            		}
            	}
            }
        }

        public boolean distributeAlternativeQuestsOverNodes(ArrayList<Quest> needsToBeDistributed, ArrayList<MapNode> remainingNodes) {
        	ArrayList<Quest> newToBeDistributed;
        	
        	for (Quest q : needsToBeDistributed) {
        		if (remainingNodes.isEmpty()) {
        			/* if there are not enough nodes remaining, we just abort this.
        			 * since this method makes no changes to the nodes, we can just
        			 * bail out and only the parent top level quest will have to be
        			 * removed from a node. the rest of the quests will remain in
        			 * memory but will not be accessible from in game. 
        			break;
        		}
        		/* distribute it while checking which of
        		 * its children need to be distributed 
        		newToBeDistributed = q.setNodeIndex(remainingNodes.get(0).index);

        		/* The node is no longer home to further
        		 * active quests. 
        		remainingNodes.remove(0);

        		/* Distribute the children of the quest
        		 * over other nodes 
        		if (!distributeAlternativeQuestsOverNodes(newToBeDistributed, remainingNodes)) {
        			/* if the subquests fail, this should fail too. 
        			return false;
        		}
        		
        	}
        	
        	return true;
        }
        
        private void updateActiveQuests(Player player) {
        	for (MapNode n : nodes) {
        		if (player.finishedQuests.contains(n.activeQuestIndex)) {
        			for (int qi : player.activeQuests) {
        				if (allQuests.get(qi).nodeIndex == n.index) {
        					n.activeQuestIndex = qi;
        				}
        			}
        		}
        	}
        	
        	/* lägg till nodens aktiva till spelarens aktiva.
        	 * eller?
        	
        }*/
        
        /*
         * --------------------
         * MAP GENERATION STUFF
         * --------------------
         */
        
        private int weightLine(MapNode a, MapNode b) {
            
        	double direction = Math.atan2(b.y-a.y, b.x-a.x);
        	double distance = Math.sqrt(Math.pow(b.x-a.x, 2) + Math.pow(b.y-a.y, 2))*24;

            double weight = distance;
       
            for (int i = 0; i < distance; i++) {
               
                int tile_x = (int) (a.x*24+12 + i * Math.cos(direction))/24;
                int tile_y = (int) (a.y*24+12 + i * Math.sin(direction))/24;
               
                switch (tiles[tile_y][tile_x]) {
                case Mountains: weight += 2*24; break;
                case Forest: weight += 1*24; break;
                case Lake: weight += 5*24;
                //case Mountains: weight *= 1.075; break;
                //case Forest: weight *= 1.001; break;
                //case Lake: weight *= 1.1; break;
                default: weight *= 1.0; break;
                //case Sand: weight *= 1.05; break;
                //case Field: weight *= 0.975; break;
                } 
            }
       
            return (int) weight;
        }
        
        private void generateMap(Player player, int rows, int cols) {

            tiles = new TerrainType[rows][cols];
            // skapa en HeightMap av seed. roughness @ 1.0f är att föredra (har balanserat mapen utifrån det).
            TerrainGenerator n = new TerrainGenerator(player.seed, 1.0f, rows, cols);
		    n.initialise();
		    float[][] grid = TerrainGenerator.getGrid();
           
            for(int i = 0; i< tiles.length; i++){
            	for(int j = 0; j< tiles[0].length; j++) {
                	if(grid[i][j] <= -1)
                		tiles[i][j] = TerrainType.Lake;
                    else if(grid[i][j] < -0.7)
                        tiles[i][j] = TerrainType.Sand;
                    else if(grid[i][j] < 0)
                        tiles[i][j] = TerrainType.Field;
                    else if(grid[i][j] < 0.5 )
                    	tiles[i][j] = TerrainType.Forest;
                    else if(grid[i][j] < 0.9 )
                        tiles[i][j] = TerrainType.Field;
                    else if(grid[i][j] < 1.1)
                        tiles[i][j] = TerrainType.Swamp;
                    else if(grid[i][j] < 1.5 )
                        tiles[i][j] = TerrainType.Field;
                    else if(grid[i][j] < 1.9 )
                        tiles[i][j] = TerrainType.Forest;
                    else if(grid[i][j] < 2.3 )
                        tiles[i][j] = TerrainType.Mountains;
                    else if(grid[i][j] < 2.6 )
                        tiles[i][j] = TerrainType.Field;
                    else if(grid[i][j] < 3)
                        tiles[i][j] = TerrainType.Forest;
                    else
                        tiles[i][j] = TerrainType.Mountains;
                }
   
            }

            nodes = new ArrayList<MapNode>();
            int maxNodes = 20;
            int cityNode = player.seed.nextInt(maxNodes);
            ArrayList<Integer> villageNodes = new ArrayList<Integer>();
            villageNodes.add(player.seed.nextInt(maxNodes));
            villageNodes.add(player.seed.nextInt(maxNodes));
            villageNodes.add(player.seed.nextInt(maxNodes));
            villageNodes.add(player.seed.nextInt(maxNodes));
            ArrayList<Integer> cabinNodes = new ArrayList<Integer>();
            
            while (nodes.size() < maxNodes) {
            	//randomiza koordinater för nästa nod
                int y = 2 + player.seed.nextInt(rows-4);
                int x = 2 + player.seed.nextInt(cols-4);
               
                boolean tooClose = false;
                for (MapNode node : nodes) {
                        double distance = Math.sqrt(Math.pow(node.x - x, 2) + Math.pow(node.y - y, 2));
                        if (distance < 5) {
                                tooClose = true;
                        }
                }

                if(!tooClose){
                    TerrainType nodeType;
                    /* Ensure that the cities, villages and cabins are placed */
                    if (nodes.size()-1 == cityNode) {
                		nodeType = TerrainType.City;
                		if (tiles[y][x] == TerrainType.Lake) {
                			continue;
                		}
                		for (int i = 0; i < 18 + player.seed.nextInt(6); i++) {
                			int rx = x + player.seed.nextInt(5) - 2;
                			int ry = y + player.seed.nextInt(3) - 1;
                			tiles[clamp(ry, 0, rows-1)][clamp(rx, 0, cols-1)] = TerrainType.City;
                		}
                	} else if (villageNodes.contains(nodes.size()-1)) {
                		if (tiles[y][x] == TerrainType.Lake) {
                			continue;
                		}
                		villageNodes.remove(new Integer(nodes.size()-1));
                		nodeType = TerrainType.Village;
                		for (int i = 0; i < 3 + player.seed.nextInt(4); i++) {
                			int rx = x + player.seed.nextInt(3) - 1;
                			int ry = y + player.seed.nextInt(3) - 1;
                			tiles[clamp(ry, 0, rows-1)][clamp(rx, 0, cols-1)] = TerrainType.Village;
                		}
                	} else if (cabinNodes.contains(nodes.size()-1)) {
                		throw new RuntimeException("LOL SHOULDN'T HAPPEN (map.java)");
                	} else {
                		/* Determine the type of the city depending on surrounding tiles */
	                	int[] surroundingTypes = new int[TerrainType.values().length];
	                	/* Collect the frequencies of all tiles in a 5×5 area. */
	                    for (int yy = clamp(y-2, 0, rows-1); yy <= clamp(y+2, 0, rows-1); yy++) {
	                    	for (int xx = clamp(x-2, 0, cols-1); xx <= clamp(x+2, 0, cols-1); xx++) {
	                    		surroundingTypes[tiles[yy][xx].ordinal()]++;
	                    	}
	                    }
	                    
	                    /* Prefer cities, then villages, then everything else. */
	                    int maxFrequency = 0;
	                	TerrainType mostFrequent = TerrainType.Field;
	                	for (TerrainType t : TerrainType.values()) {
	                		if (surroundingTypes[t.ordinal()] > maxFrequency) {
	                			maxFrequency = surroundingTypes[t.ordinal()];
	                			mostFrequent = t;
	                		}
	                	}
	                	nodeType = mostFrequent;
                	}
                	nodes.add(new MapNode(nodes.size(), x, y, nodeType, -1, player, allPets));
            	}
        	}

        }
        
        private void computePaths()
        {
            ArrayList<Edge> potentialPaths = new ArrayList<Edge>();
            for (int i = 0; i < nodes.size(); i++) {
                    for (int j = i+1; j < nodes.size(); j++) {
                            int terrainWeight = weightLine(nodes.get(i), nodes.get(j));
                            potentialPaths.add(new Edge(nodes.get(i), nodes.get(j), terrainWeight));
                    }
            }
            
            PriorityQueue<Edge> edgeList = new PriorityQueue<Edge>(potentialPaths);
            
            while (!edgeList.isEmpty()) {
            	Edge e = edgeList.poll();
            	if (!connected(e.a, e.b)) {
            		edges.add(e);
            	}
            }
        }
        
        

        private void computeDistanceToNodes()
        {
        	nodes.get(0).distance = 0;
        	PriorityQueue<MapNode> toVisit = new PriorityQueue<MapNode>(nodes);
        	ArrayList<MapNode> visited = new ArrayList<MapNode>();
        	
        	double farthest = 0;
        	
        	while (!toVisit.isEmpty()) {
        		MapNode current = toVisit.poll();
        		visited.add(current);
        		
        		for (Edge e : edges) {
        			if (e.involves(current)) {
        				double distanceFromHere = current.distance + e.weight;
        				
        				if (distanceFromHere < e.other(current).distance) {
        					e.other(current).distance = distanceFromHere;
        				}
        			}
        			
        		}

        		toVisit.clear();
        		for (MapNode n : nodes) {
        			if (!visited.contains(n)) {
        				toVisit.add(n);
        			}
        		}
        		
        		farthest = current.distance;
        	}
        	
        	// Sätter distance så att den fördelas jämnt mellan alla noder
        	PriorityQueue<MapNode> orderedNodes = new PriorityQueue<MapNode>(nodes);
        	for (double number = 0; !orderedNodes.isEmpty(); number++) {
        		MapNode n = orderedNodes.poll();
        		n.distance = number/(nodes.size() - 1);
        	}
        }
        
        
        
        int clamp(int i, int min, int max) {
        	return Math.max(min, Math.min(max, i));
        }

        public void getPetList(){
        	
        	allPets.add(new Baconator("Baconator", 0));
        	allPets.add(new Bear("Bear", 0));
        	allPets.add(new EvilBunny("Evil Bunny", 0));
        	allPets.add(new Manet("Manet", 0));
        	allPets.add(new MrFox("Mr Fox", 0));
        	allPets.add(new Pittri("Pittri", 0));
        	allPets.add(new Salamander("Salamander", 0));
        	allPets.add(new Seppo("Seppo", 0));
        	allPets.add(new SirCrab("Sir Crab", 0));
        	allPets.add(new Sköldpadduru("Skölpadduru", 0));
        	allPets.add(new Troll("Troll", 0));
        	allPets.add(new Vfoggel("Vfoggel", 0));
        	allPets.add(new Zebru("Zebru", 0));
      
        }
}

